package classes.libsvm;
import java.util.*;

public class RelationKernel
{
  static final int DEFAULT_FORE = 4;
  static final int DEFAULT_INTRA = 4;
  static final int DEFAULT_AFTER = 4;
  static final double DEFAULT_LAMBDA = 0.75;
  static final boolean DEFAULT_CACHE = true; 
  static final boolean DEFAULT_NORM = true; 

  // max length of fore subseq
  int m_nFore;
  // max length of intra subseq
  int m_nIntra;
  // max length of after subseq
  int m_nAfter;
  // gap penalty
  double m_lambda;
  // true if cached self kernels
  boolean m_bCache;
  // true if normalized kernels
  boolean m_bNorm;
	
  protected HashMap m_mapStoK;

  public RelationKernel(int nFore, int nIntra, int nAfter,
			double lambda, boolean bCache, boolean bNorm)
  {
    m_nFore = nFore;
    m_nIntra = nIntra;
    m_nAfter = nAfter;
    m_lambda = lambda;
    m_bCache = bCache;
    m_bNorm = bNorm;

    m_mapStoK = new HashMap();
  }

  public RelationKernel() 
  {
    m_nFore = DEFAULT_FORE;
    m_nIntra = DEFAULT_INTRA;
    m_nAfter = DEFAULT_AFTER;
    m_lambda = DEFAULT_LAMBDA;
    m_bCache = DEFAULT_CACHE;
    m_bNorm = DEFAULT_NORM;

    m_mapStoK = new HashMap();
  }


  /**
     Computes the normalized string kernel between two strings.
     @param s1 string 1
     @param s2 string 2
     @return normalized value, with 1 for exact match.
  */
  public double normKernel(String[][] s1, String[][] s2) 
  {
    double k1 = selfKernel(s1);
    double k2 = selfKernel(s2);
    
    double k = kernel(s1, s2);

    // normalize
    return k / Math.sqrt (k1 * k2);				
  }
  
  
  public double selfKernel(String[][] s)
  {
    if (m_bCache) {
      // get string representation of relation instance
      String strText = "";
      for (int i = 0; i < s.length; i++)
	strText += s[i][0] + " ";
      // get cached value
      Double dblk = (Double) m_mapStoK.get(strText);
      if (dblk == null) {
	double k = kernel(s, s);
	m_mapStoK.put(strText, new Double(k));
	return k;
      }
      return dblk.doubleValue();
    }

    return kernel(s, s);
  }
  

  public double kernel(String[][] s1, String[][] s2)
  {
    int e1 = getLeftEntity(s1);
    assert e1 != -1;
    int e2 = getRightEntity(s1);
    assert e2 > e1;
    int f1 = getLeftEntity(s2);
    assert f1 != -1;
    int f2 = getRightEntity(s2);
    assert f2 > f1;

    String[][] fore1 = new String[e1][];
    System.arraycopy(s1, 0, fore1, 0, e1);
    String[][] fore2 = new String[f1][];
    System.arraycopy(s2, 0, fore2, 0, f1);
    //    normalize(fore1, fore2);

    /*
    for (int i = 0; i < fore1.length; i++)
      System.out.print(fore1[i] + " ");
    System.out.println();
    for (int i = 0; i < fore2.length; i++)
      System.out.print(fore2[i] + " ");
    System.out.println();
    */

    String[][] intra1 = new String[e2 - e1 - 1][];
    System.arraycopy(s1, e1 + 1, intra1, 0, e2 - e1 -1);
    String[][] intra2 = new String[f2 - f1 - 1][];
    System.arraycopy(s2, f1 + 1, intra2, 0, f2 - f1 -1);
    //    normalize(intra1, intra2);

    /*
    for (int i = 0; i < intra1.length; i++)
      System.out.print(intra1[i] + " ");
    System.out.println();
    for (int i = 0; i < intra2.length; i++)
      System.out.print(intra2[i] + " ");
    System.out.println();
    */

    String[][] after1 = new String[s1.length - e2 - 1][];
    for (int i = 0; i < after1.length; i++)
      after1[i] = s1[s1.length - 1 - i]; // mirror
    //    System.arraycopy(s1, e2 + 1, after1, 0, s1.length - e2 - 1);
    String[][] after2 = new String[s2.length - f2 - 1][];
    for (int i = 0; i < after2.length; i++)
      after2[i] = s2[s2.length - 1 - i]; // mirror
    //    System.arraycopy(s2, f2 + 1, after2, 0, s2.length - f2 - 1);
    //    normalize(after1, after2);

    int nLenIntra = Math.min(Math.max(m_nIntra,
				      Math.max(m_nFore - 1, m_nAfter - 1)),
			     Math.min(intra1.length, intra2.length));
    double[] sk = stringKernel(intra1, intra2, nLenIntra, 1.0);
    double[] intraK = new double[nLenIntra];
    for (int i = 0; i < intraK.length; i++) {
      intraK[i] = sk[i] *
	common(s1[e1], s2[f1]) * 
	common(s1[e2], s2[f2]) *
	Math.pow(m_lambda, intra1.length + 2 + intra2.length + 2);
      //      System.out.println("intraK[" + i + "] = " + intraK[i]);
    }

    
    double foreKernel = foreKernel(fore1, fore2, intraK);
    //    System.out.println("fore = " + foreKernel);
    double intraKernel = intraKernel(intraK);
    //    System.out.println("intra = " + intraKernel);
    double afterKernel = afterKernel(after1, after2, intraK);
    //    System.out.println("after = " + afterKernel);
    double modKernel = 0.0;
    if (intra1.length == 0 && intra2.length == 0)
      modKernel = common(s1[e1], s2[f1]) * common(s1[e2], s2[f2]) *
	Math.pow(m_lambda, 2 + 2);
    //    System.out.println("mod = " + modKernel);

    return foreKernel + intraKernel + afterKernel + modKernel;
  }


  protected double foreKernel(String[][] fore1, String[][] fore2, 
			      double[] intraK)
  {
    double k = 0.0;
    double[] foreK = sKernel(fore1, fore2, m_nFore - 1, m_lambda);

    for (int i = 1; i < m_nFore; i++) {
      for (int j = 1; j <= m_nFore - i && j <= intraK.length; j++)
	k = k + foreK[i - 1] * intraK[j - 1];
    }

    return k;
  }


  protected double intraKernel(double[] intraK)
  {
    double k = 0.0;
    for (int i = 0; i < m_nIntra && i < intraK.length; i++)
      k = k + intraK[i];

    return k;
  }


  protected double afterKernel(String[][] after1, String[][] after2, 
			       double[] intraK)
  {
    //    String[][] aft1 = mirror(after1);
    //    String[][] aft2 = mirror(after2);
    double k = 0.0;
    double[] afterK = sKernel(after1, after2, m_nAfter - 1, m_lambda);

    for (int i = 1; i < m_nAfter; i++) {
      for (int j = 1; j <= m_nAfter - i && j <= intraK.length; j++)
	k = k + afterK[i - 1] * intraK[j - 1];
    }

    return k;
  }


  protected double[] stringKernel(String[][] s, String[][] t, 
				  int n, double lambda)
  {
    int slen = s.length;
    int tlen = t.length;
    
    double[][] K = new double[n + 1][slen * tlen];
    
    for (int j = 0; j < slen; j++)
      for (int k = 0; k < tlen; k++)
	K[0][k * slen + j] = 1;
    
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < slen - 1; j++) {
	double sum = 0.0;
	for (int k = 0; k < tlen - 1; k++) {
	  sum = lambda * (sum + 
			  lambda * common(t[k], s[j])  * K[i][k * slen + j]);
	  K[i + 1][(k + 1) * slen + j + 1] = 
	    lambda * K[i + 1][(k + 1) * slen  + j] + sum;
	}
      }
    }

    double[] result = new double[n];
    for (int l = 0; l < result.length; l++) {
      result[l] = 0.0;
      for (int j = 0; j < slen; j++) {
	for (int k = 0; k < tlen; k++)
	  result[l] = result[l] + lambda * lambda * common(t[k], s[j]) 
	    * K[l][k * slen + j];
      }
    }

    //    double powl = Math.pow(lambda, n);
    //    return r / (powl * powl);
    return result;
  }


  protected double[] sKernel(String[][] s, String[][] t, 
			     int n, double lambda)
  {
    double r = 0.0;
    int slen = s.length;
    int tlen = t.length;
    
    double[][] K = new double[n + 1][(slen + 1) * (tlen + 1)];
    
    for (int j = 0; j < slen + 1; j++)
      for (int k = 0; k < tlen + 1; k++)
	K[0][k * (slen + 1) + j] = 1;
    
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < slen; j++) {
	double sum = 0.0;
	for (int k = 0; k < tlen; k++) {
	  sum = lambda * (sum + 
			  lambda * common(t[k], s[j]) * K[i][k * (slen + 1) + j]);
	  K[i + 1][(k + 1) * (slen + 1) + j + 1] = 
	    lambda * K[i + 1][(k + 1) * (slen + 1) + j] + sum;
	}
      }
    }

    //    double powl = Math.pow(lambda, n);
    //    return K[n][tlen * (slen + 1) + slen] / (powl * powl);
    double[] result = new double[n];
    for (int i = 0; i < result.length; i++)
      result[i] = K[i + 1][tlen * (slen + 1) + slen];
    return result;
  }


  protected int common(String[] s, String[] t)
  {
    assert s.length == t.length;
    int nCount = 0;
    for (int i = 0; i < s.length; i++)
      if (s[i] != null && s[i] == t[i])
	nCount++;

    return nCount;
  }


  protected int getLeftEntity(String[][] s)
  {
    for (int i = 0; i < s.length; i++)
      if (s[i][0].equals("<p1>"))
	return i;
    return -1;
  }


  protected int getRightEntity(String[][] s)
  {
    for (int i = s.length - 1; i >= 0; i--)
      if (s[i][0].equals("<p2>"))
	return i;
    return -1;
  }


  protected void normalize(String[][] s1, String[][] s2)
  {
    for (int i = 0; i < s1.length; i++)
      for (int j = 0; j < s2.length; j++)
	if (s1[i][0].equals(s2[j][0]))
	  s2[j][0] = s1[i][0];
  }


  protected String[][] mirror(String[][] s)
  {
    String[][] t = new String[s.length][];
    for (int i = 0; i < s.length; i++)
      t[s.length - i - 1] = s[i];

    return t;
  }


  public static void main (String[] args)
  {
    String per = "per";
    String gpe = "gpe";
    String[][] s1 = {{"c", null}, {"c", null}, {"c", null},
		     {"<p1>", per}, 
		     //		     {"c", null}, {"b", null}, {"c", null},
		     {"<p2>", gpe},
		     {"c", null}, {"c", null}, {"c", null}};

    String[][] s2 = {{"a", null}, {"a", null}, {"a", null},
		     {"<p1>", per}, 
		     //		     {"a", null}, {"b", null}, {"a", null},
		     {"<p2>", gpe},
		     {"a", null}, {"a", null}, {"a", null}};

    RelationKernel rk = new RelationKernel();
    System.out.println(rk.kernel(s1, s2));
    rk.m_lambda = 1.0;
    System.out.println(rk.kernel(s1, s2));
  }

}

